#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/**
 * 后序递归法：使用前序也行，后序也行，前序求深度，后序求高度。从最后往前判断的话已经保存了最下层的状态了。所以不需要回溯
 */
class Test01{
public:
	int getDepth(TreeNode* node){
		if(node == NULL){
			return 0;
		}
		int leftDepth = getDepth(node->left);
		int righatDepth = getDepth(node->right);
		return 1 + max(leftDepth,righatDepth);
	}
	int maxDepth(TreeNode* root){
		return getDepth(root);
	}
};

/**
 * 前序递归法：使用前序也行，后序也行，前序求深度，后序求高度。从前往后探测，是需要回溯的。
 */
class Test02{
public:
	int result;
	void getDepth(TreeNode* node,int depth){
		result = depth > result ? depth :result; // 中
		if(node->left == NULL && node->right == NULL){
			return;
		}
		if(node->left){
			depth++;
			getDepth(node->left,depth);
			depth--;
		}
		if(node->right){
			depth++;
			getDepth(node->right,depth);
			depth--;
		}
		return;
	}
	int maxDepth(TreeNode* root){
		result = 0;
		if(root == NULL){
			return result;
		}
		getDepth(root,1);
		return result;
	}
};
/**
 * 迭代法：就是层序遍历
 */
class Test03{
public:
	int maxDepth(TreeNode* root){
		if(root == NULL) return 0;
		queue<TreeNode*> que;
		que.push(root);
		int depth = 0;
		while(!que.empty()){
			int size = que.size();
			depth++;
			while(size--){
				TreeNode* node = que.front();que.pop();
				if(node->left){
					que.push(node->left);
				}
				if(node->right){
					que.push(node->right);
				}
			}
		}
		return depth;
	}
};
class Test{
public:
	int getdepth(TreeNode* node){
		queue<TreeNode*> que;
		que.push(node);
		int depth = 0;
		while(!que.empty()){
			int size = que.size();
			depth++;
			while(size--){
				TreeNode* cur = que.front();que.pop();
				if(cur->left){
					que.push(cur->left);
				}
				if(cur->right){
					que.push(cur->right);
				}
			}
		}
		return depth;		
	}
};
